//连接两个有序的单向链表
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

// 节点对应的结构体
typedef struct Node
{
    int num;            // 每个节点中存储的数据，可以有多个
    struct Node* pNext; // 用于保存下一个节点(结构体)的指针
}NODE;

/* 
* 函数功能：  创建一个新节点
* int n：     当前节点的数据
* 返回类型：  成功:返回当前节点的首地址, 失败:NULL
*/
NODE* createNode(int n)
{
    // 创建新节点
    NODE* pNew = (NODE*)malloc(sizeof(NODE));
    if (NULL == pNew)
    {
        printf("createNode %d fail: %s!\n", n, strerror(errno));
        return NULL;
    }

    // 初始化新节点中的成员变量
    pNew->num = n;
    pNew->pNext = NULL;

    // 返回当前节点的首地址
    return pNew;
}

/*
* 函数功能：  输出整个链表
* NODE* head：链表首地址
* 返回类型：  无
*/
void displayList(NODE* head)
{
    NODE* p = head;
    while (p != NULL)
    {
        printf("%d ", p->num);
        p = p->pNext;
    }
    printf("\n");
}

/*
* 函数功能：   获取链表尾节点的指针
* NODE* head： 链表首节点的地址
* 返回类型：   返回尾节点指针
*/
NODE* getTailNode(NODE* head)
{
    if (head == NULL)
    {
        return NULL;
    }

    while(head->pNext != NULL)
    {
        head = head->pNext;
    }

    return head;
}

/*
* 函数功能：   在原链表尾节点之后插入一个新节点
* int n：      新节点的数据
* NODE* head： 原链表首节点的地址
* 返回类型：   返回新链表的首节点
*/
NODE* insert_tail(int n, NODE* head)
{
    // 创建新节点
    NODE* pNew = createNode(n);
    if (pNew == NULL)
    {
        return head;
    }

    // 获取原链表尾节点的指针
    NODE* pTail = getTailNode(head);
    if (pTail == NULL)
    {
        return pNew;
    }

    // 将原链表尾节点和新节点连接
    pTail->pNext = pNew;
    
    return head;
}

/*
* 函数功能：     合并两个有序的链表，并且合并过程中保持有序
* NODE* head2： 链表1首节点的地址
* NODE* head2： 链表2首节点的地址
* 返回类型：     返回合并后链表的首节点
*/
NODE* connectList(NODE* p1, NODE* p2) {
    // 处理空链表情况
    if (!p1) return p2;
    if (!p2) return p1;

    NODE* head = p1;  // 结果链表的头节点
    NODE* prev = NULL; // 前驱节点

    while (p1 && p2) {
        if (p1->num <= p2->num) 
        {
            prev = p1;
            p1 = p1->pNext;
        } 
        else 
        {
            NODE* tmp = p2;
            p2 = p2->pNext;
            
            if (!prev) 
            {  // 在头部插入
                tmp->pNext = p1;
                head = tmp;
            } 
            else 
            {  // 在中间插入
                tmp->pNext = p1;
                prev->pNext = tmp;
            }
            prev = tmp;  // 更新前驱节点
        }
    }

    // 连接剩余节点
    if (p2) {
        prev->pNext = p2;
    }

    return head;
}
int main(int argc, char const *argv[])
{
    NODE *head1 = NULL;
    NODE *head2 = NULL;

    head1 = insert_tail(1,head1);
    head1 = insert_tail(3,head1);
    head1 = insert_tail(4,head1);
    head1 = insert_tail(5,head1);

    head2 = insert_tail(2,head2);
    head2 = insert_tail(5,head2);
    head2 = insert_tail(6,head2);
    head2 = insert_tail(8,head2);
    
    displayList(head1);
    displayList(head2);

    head1 = connectList(head1,head2);
    displayList(head1);
    
    return 0;
}

